package hashUtil;

/**
 * @Author: sun
 * @Description:
 * @Data: create in 15:21 2018/12/17
 * @Modfied by:
 */

import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import org.geotools.geometry.jts.JTSFactoryFinder;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;

/**
 * Created by xd on 2016/5/14.
 */


public class GeoHashUtil {

    /**
     * The characters used in base 32 representations.
     */
    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

    /**
     * The standard practical maximum length for geohashes.char num
     */
    public static final int MAX_HASH_LENGTH = 12;

    /**
     * To control the Search Deepth.Unit is bit
     * Default value is equal as MAX_Hash_LENGTH
     */
//    public static final int SEARCH_DEEPTH = 6 * 5;

    /**
     * 将经纬度坐标转化为一个hash值，hash 为long 类型(64bit)，
     * 但是只使用了前(5 * MAX_HASH_LENGTH) bit 来存储信息。
     * 求hash值的过程大致是如下过程：交叉取经纬度的信息，如果经度是
     * 在当前区域的正中间或者右边部分，该位取1，否则取0；如果维度是
     * 在当前区域的正中间或者上面部分，该位取1，否则取0；并将当前区
     * 域缩小至原来的1/4，作为新的区域。这样循环，直到达到指定的精度.
     * <pre>
     *    0    1
     * ┌ -- ┬ -- ┐
     * |    | 11 | 1
     * ├ -- ┼ -- ┤
     * | 00 |    | 0
     * └ -- ┴ -- ┘</pre>
     * @param longitude 经度
     * @param latitude 纬度
     * @return hash
     */
    public static long LongLatToHash(double longitude, double latitude) {
        boolean isEven = true;
        double minLat = -90.0, maxLat = 90.0;
        double minLon = -180.0, maxLon = 180.0;
        long bit = 0x8000000000000000L;
        long g = 0x0L;

        long target = 0x8000000000000000L >>> (5 * MAX_HASH_LENGTH);
        while (bit != target) {
            if (isEven) {
                double mid = (minLon + maxLon) / 2;
                if (longitude >= mid) {
                    g |= bit;//置1
                    minLon = mid;
                } else{
                    maxLon = mid;
                }
            } else {
                double mid = (minLat + maxLat) / 2;
                if (latitude >= mid) {
                    g |= bit;//置1
                    minLat = mid;
                } else{
                    maxLat = mid;
                }
            }

            isEven = !isEven;
            bit >>>= 1;
        }
        return g;

    }

    /**
     * 将hash转化为经纬度，传入的hash 是利用之前的LongLatToHash(double, double)获得，
     * 所以这里的hash 只取前5 * MAX_HASH_LENGTH bit。返回的是经纬度点坐标，{@link LongLat}类型。
     * 主要的操作过程与 LongLatToHash方法大致是相反的。大概采用二分的思想。
     * @param geohash hash值，long类型
     * @return LongLat 点的经纬度坐标
     */
    // Translated to java from:
    // geohash.js
    // Geohash library for Javascript
    // (c) 2008 David Troy
    // Distributed under the MIT License
    public static LongLat HashToLongLat(Long geohash) {
        //to alternate longtitude and latitude
        boolean isEven = true;
        double[] lat = new double[2];
        double[] lon = new double[2];
        lat[0] = -90.0;//纬度的左边界
        lat[1] = 90.0;//纬度的右边界
        lon[0] = -180.0;//经度的左边界
        lon[1] = 180.0;//经度的右边界
        //按位循环，逐渐逼近，最终经纬度的左右边界逐渐靠近，并趋于相等。
        long bit = 0x8000000000000000L;
        for (int i = 0; i < 5 * MAX_HASH_LENGTH; i++) {
            boolean bitValue = (geohash & bit) != 0;
            if (isEven) {
                refineInterval(lon, bitValue);//根据当前位，来判断经度的取值范围
            } else {
                refineInterval(lat, bitValue);
            }
            isEven = !isEven;
            bit >>>= 1;
        }
        double resultLat = (lat[0] + lat[1]) / 2;//取均值
        double resultLon = (lon[0] + lon[1]) / 2;
        return new LongLat(resultLon, resultLat);
    }

    /**
     * 当前位bitValue 为1时，将左边或者下边界向中间缩减，否则，将右边界或上边界
     * 向中间缩减。
     * @param interval 经度(或者纬度)的最小和最大值区间，数组长度为2
     * @param bitValue 当前位
     */
    private static void refineInterval(double[] interval, boolean bitValue) {
        if (bitValue)
            interval[0] = (interval[0] + interval[1]) / 2;
        else
            interval[1] = (interval[0] + interval[1]) / 2;
    }

    /**
     * Returns the maximum length of hash that covers the bounding box. If no
     * hash can enclose the bounding box then 0 is returned.
     * 将矩形框{@link BBox} 转化为前缀{@link BBoxToPrefix}，如果没有公共前缀，返回
     * 的前缀length = 0。<br>
     * 主要思路是：取左下和右上角的2个点，得到它们对应的hash值，返回
     * 的就是这两个hash的公共前缀。<br>
     * 需要说明的是，在这个方法中，返回的公共前缀代表的实际矩形区域是要比传入的参数
     * <i> bBox </i>表示的矩形更大。
     * @param bBox 矩形框，BBox类型
     * @return 矩形框对应的前缀
     */
    public static BBoxPrefix BBoxToPrefix(BBox bBox) {
        int prefixLength = 0;
        long mask = 0x8000000000000000L;
        long bottomLeftHash = GeoHashUtil.LongLatToHash(bBox.bottomLeftLon,bBox.bottomLeftLat);
        long topRightHash = GeoHashUtil.LongLatToHash(bBox.topRightLon,bBox.topRightLat);
//        System.out.println(bBox.topRightLon+" "+bBox.topRightLat);
//        System.out.println(Long.toBinaryString(bottomLeftHash));
//        System.out.println(Long.toBinaryString(topRightHash));
        long BBoxPrefixXor = bottomLeftHash ^ topRightHash;
        for (int i = 0; i < MAX_HASH_LENGTH * 5; i++) {
            if ((mask & BBoxPrefixXor) != 0) {
                mask <<= 1;
                break;
            }
            //注意，这里是带符号右移
            mask >>= 1;
            prefixLength++;
        }
        //返回掩码后的结果
        BBoxPrefix result = new BBoxPrefix(bottomLeftHash & mask,prefixLength);
        return result;
    }

    /**
     * 将一个前缀{@link BBoxPrefix} 转换为一个矩形框区域{@link BBox}。
     * 一个BBox对象经过 <i> BBoxToPrefix(BBox) </i>之后得到的BBoxPrefix，
     * 在将BBoxPrefix经过方法<i>PrefixToBBox(BBoxPrefix)</i>所返回的结果newBox与
     * 之前的BBox在很大概率上是不同的，并且newBox > BBox
     * @param bBoxprefix 前缀
     * @return 返回BBox 实例
     */
    public static BBox PrefixToBBox(BBoxPrefix bBoxprefix) {
        LongLat bottomLeft = HashToLongLat(bBoxprefix.prefix);
        long max = (0xffffffffffffffffL >>> bBoxprefix.length) + bBoxprefix.prefix;
        LongLat topRight = HashToLongLat(max);
//        System.out.println(bottomLeft);
//        System.out.println(topRight);
        //注意： prefix 是对应左下角点，max 对应的是右上角的点。
        BBox result = new BBox(bottomLeft.getLongitude(),bottomLeft.getLatitude(),
                topRight.getLongitude(),topRight.getLatitude());
        return result;
    }

    /**
     * 利用前缀来计算对应矩形框的面积
     * @param bBoxprefix 前缀
     * @return 面积
     */
    public static double GetArea4Prefix(BBoxPrefix bBoxprefix){
    	BBox box = PrefixToBBox(bBoxprefix);
    	double result = 0.0;
    	double len = box.topRightLon - box.bottomLeftLon,
    			high = box.topRightLat - box.bottomLeftLat;
    	result = len * high;
    	result = (result < 0)? -result:result;
    	return result;
    }


    public static void main(String[] args) throws ParseException {

//    	searchWithPoly("0 0,10.32 1.2, 9.32 16.12, 0.32 15.12,0 0", 10);

	}
}
